package leetcode_core.dataStruct;

public class MinPQ <Key extends Comparable<Key>>{
    private int size;
    private Key[] pq;

    public MinPQ(int cap){
        pq = (Key[]) new Comparable[cap+1];
    }
    //将key插入到小顶堆中
    public void insert(){

    }
    //取当前队列中的最小值
    public Key min(){
        return pq[1];
    }
    //删除堆顶并且返回
    public Key deleteMin(){
        return null;
    }
    /*先处理上浮和下沉的逻辑*/
    //上浮
    private void swim(int x){
        //当上浮到1的时候,就代表着最上层没法再上浮了,如果这个数比它的父节点还要小,那就继续浮
        while (x>1 && isBigger(parent(x),x)){
            swap(parent(x),x);
            x = parent(x);
        }
    }
    //下沉
    private void sink(int x){
        while (left(x) <= size){
            //假设左边节点比较小
            int min = left(x);
            //如果右边节点存在,那么比一下
            if(right(x) <= size && isBigger(min,right(x))){
                min = right(x);
            }
            //如果节点比两个孩子都小
            if(isBigger(min,x)) {
                break;
            }
            swap(x,min);
            x = min;
        }
    }

    private boolean isBigger(int x,int y){
        return pq[x].compareTo(pq[y])>0;
    }

    private void swap(int i,int j){
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }

    private int parent(int root){
        return root/2;
    }
    private int left(int root){
        return root*2;
    }
    private int right(int root){
        return root*2+1;
    }

}
